package cn.java.sort;

import java.util.Arrays;

/**
 * 选择排序 2019-11-03
 * 
 * @author zjb
 *
 */
public class SelectSort {

	/**
	 * 选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下。
	 * 首先在未排序序列中找到最小的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，放到排序序列未尾。
	 * 以此类推，直到所有的元素均排序完毕。 
	 *    选择排序的交换操作介于0和(n-1)次之间; 
	 *    选择排序的比较操作为n(n-1)/2次之间;
	 *    选择排序的赋值操作介于0和3(n-1)次之间; 
	 *    其平均复杂度为O(n2)
	 */

	/**
	 * 选择排序 一
	 * 
	 * @param source
	 *            --待排序的数组
	 */
	public static void selectSort(int[] source) {

		for (int i = 0; i < source.length; i++) {
			for (int j = i + 1; j < source.length; j++) {
				if (source[i] > source[j]) {
					swarp(source, i, j);
				}
			}
		}
	}

	private static void swarp(int[] source, int x, int y) {
		int temp = source[x];
		source[x] = source[y];
		source[y] = temp;
	}

	/**
	 * 选择排序二
	 * 
	 * @param arr
	 *            --待排序的数组
	 * @param n
	 *            --待排序数组的长度
	 */
	public static void selectSort(int[] arr, int n) {
		int i; // 有序区末尾的位置
		int j; // 无序区起始的位置
		int min; // 无序区最小的位置

		for (i = 0; i < n; i++) {

			min = i;

			// 找出arr[i+1]...a[n]之间的最小元素，并赋值给min
			for (j = i + 1; j < n; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}

			// 若min!=i,则交换arr[i]和a[min]
			// 交换之后，保证arr[0] ... arr[i]之间的元素是有序的
			if (min != i) {
				int temp = arr[i];
				arr[i] = arr[min];
				arr[min] = temp;
			}
		}
	}

	public static void main(String[] args) {
      int[] arr= {1,3,5,7,4,2};
      selectSort(arr,arr.length);
      System.out.println(Arrays.toString(arr));
	}
}
